#include<vector>
#include<iostream>

using namespace std;
void helper(vector<int> &array, int startIdx, int endIdx) {
  if (startIdx >= endIdx) {
    return;
  }

  int pivot = startIdx;
  int l = startIdx + 1;
  int r = endIdx;

  while (l <= r) {  
    if (array[l] > array[pivot] && array[r] < array[pivot]) {
      swap(array[l], array[r]);
    }
    if (array[l] <= array[pivot]) {
      ++l;
    }
    if (array[r] >= array[pivot]) {
      --r;
    }
  }

  swap(array[pivot], array[r]);

  helper(array, startIdx, r - 1);
  helper(array, r + 1, endIdx);
}

void quickSort(vector<int> &array) {
  helper(array, 0, array.size() - 1);
}
int main(int argc, char const *argv[]) {
  vector<int> array {1, 7, 2, 6, 3, 9, 6, 4, 20, -6, 5};
  quickSort(array);
  for (int i : array) {
    cout<<i<<", ";
  }
  return 0;
}
